package org.example.leetCode;

/**
 * 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 */
public class Code37 {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0);
    }

    /**
     * 回溯算法解决数独
     * @param board 数独棋盘
     * @param row 当前行
     * @param col 当前列
     * @return 是否找到解
     */
    private boolean backtrack(char[][] board, int row, int col) {
        // 如果列越界，转到下一行第一列
        if (col == 9) {
            return backtrack(board, row + 1, 0);
        }

        // 如果行越界，说明数独已解完
        if (row == 9) {
            return true;
        }

        // 如果当前位置已有数字，处理下一个位置
        if (board[row][col] != '.') {
            return backtrack(board, row, col + 1);
        }

        // 尝试填入数字1-9
        for (char ch = '1'; ch <= '9'; ch++) {
            // 检查是否可以填入该数字
            if (isValid(board, row, col, ch)) {
                // 做选择
                board[row][col] = ch;

                // 递归处理下一个位置
                if (backtrack(board, row, col + 1)) {
                    return true;
                }

                // 撤销选择（回溯）
                board[row][col] = '.';
            }
        }

        // 1-9都尝试过都不行，返回false
        return false;
    }

    /**
     * 检查在指定位置填入指定数字是否合法
     * @param board 数独棋盘
     * @param row 行索引
     * @param col 列索引
     * @param ch 要填入的字符
     * @return 是否合法
     */
    private boolean isValid(char[][] board, int row, int col, char ch) {
        // 检查行是否有重复
        for (int j = 0; j < 9; j++) {
            if (board[row][j] == ch) {
                return false;
            }
        }

        // 检查列是否有重复
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == ch) {
                return false;
            }
        }

        // 检查3x3宫格是否有重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == ch) {
                    return false;
                }
            }
        }

        return true;
    }
}
